#ifndef AVL_TREE_H
#define AVL_TREE_H

#include <iostream>
using namespace std;

template <class Comparable>
class AvlTree
{
  public:
 	struct AvlNode
	{
		Comparable element;
		AvlNode *left;
		AvlNode *right;
		int height;

		AvlNode(const Comparable &theElement, AvlNode *lt, 
				AvlNode *rt, int h = 0) 
			: element(theElement), left(lt), right(rt), height(h) {}
		//friend class AvlTree;
	};
  public:
  	explicit AvlTree();
	AvlTree(const AvlTree & rhs); 
	~AvlTree();

	const Comparable & findMin() const;
	const Comparable & findMax() const;
	//const Comparable & find(const Comparable &x) const;
	bool contains(const Comparable &x) const;
	bool isEmpty() const;
	void printTree() const;
	int height(AvlNode *t) const;

	void makeEmpty();
	void insert(const Comparable &x);
	void remove(const Comparable &x);

	void rotateWithLeftChild(AvlNode * &k2) const;
	void rotateWithRightChild(AvlNode * &k1) const;
	void doubleWithLeftChild(AvlNode * &k3) const;
	void doubleWithRightChild(AvlNode * &k3) const;

	const AvlTree & operator=(const AvlTree & rhs);
	int max(int a, int b) const;
  private:
 	AvlNode	*root;
	//const Comparable ITEM_NOT_FOUND;
	
	const Comparable & elementAt(AvlNode *t) const;

	void insert(const Comparable &x, AvlNode * &t) const;
	void remove(const Comparable &x, AvlNode * &t) const;
	AvlNode * findMin(AvlNode *t) const
	{
		if (t == NULL)	
			return NULL;
		if (t->left == NULL)
			return t;
		return findMin(t->left);
	}
	AvlNode * findMax(AvlNode *t) const
	{
		if (t != NULL)
			while (t->right != NULL)
				t = t->right;

		return t;
	}
	bool contains(const Comparable &x, AvlNode *t) const;
	//AvlNode * find(const Comparable &x, AvlNode *t) const;
	
	void makeEmpty(AvlNode * &t) const;
	void printTree(AvlNode *t) const;
	AvlNode *clone(AvlNode *t) const
	{
		if (t == NULL)
			return NULL;
		else 
			return new AvlNode(t->element, clone(t->left), clone(t->right), 
					t->height);
	}
};

#endif
